package com.leetcode.根据数据结构分类.数组;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author: xiaomi
 * @date: 2021/3/14
 * @description: 剑指 Offer 61. 扑克牌中的顺子
 * https://leetcode-cn.com/problems/bu-ke-pai-zhong-de-shun-zi-lcof/
 */
public class A_剑指Offer61_扑克牌中的顺子 {

    static A_剑指Offer61_扑克牌中的顺子 action = new A_剑指Offer61_扑克牌中的顺子();

    public static void main(String[] args) {
        test1();
    }

    public static void test1() {
        // 3
        int[] nums = new int[]{11, 0, 9, 0, 0};
        boolean res = action.isStraight(nums);
        System.out.println("res = " + res);
        //[]
    }

    /**
     * 1.排序；
     * 2.滑动窗口
     * 这个思路其实并不优秀，而且代码写起来也很不优雅
     *
     * @param nums
     * @return
     */
    public boolean isStraight(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);
        int zeroCount = 0;
        //找到 0 的数量
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                zeroCount++;
            } else {
                break;
            }
        }

        //开始滑动窗口
        int begin = zeroCount, end = begin + 1;
        int midCount = 0;
        //增加去重判断
        //int[] recordArr= new int[13];
        while (end < len) {
            //增加去重判断
            if (nums[end - 1] == nums[end]) {
                return false;
            }
            if (nums[end - 1] == nums[end] - 1) {
                begin++;
            } else {
                if (nums[end] - nums[begin] - midCount > zeroCount + 1) {
                    return false;
                }
                midCount++;
            }
            end++;
        }
        return true;
    }


    /**
     * 1。使用 set 记录是否重复；
     * 2.找出 max min (遇到王就跳过),规律是：max-min<5
     *
     * @param nums
     * @return
     */
    public boolean isStraight2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int len = nums.length;
        int max = 0, min = 13;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                continue;
            }
            if (set.contains(nums[i])) {
                return false;
            }else{
                set.add(nums[i]);
            }
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        return max - min < 5;
    }

    /**
     * 在 2 的规律下，用数组替代 set
     * --
     * 这样的效率就高于 set 了
     * @param nums
     * @return
     */
    public boolean isStraight3(int[] nums) {
        int[] recorder = new int[13];
        int len = nums.length;
        int max = 0, min = 13;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 0) {
                continue;
            }
            if (recorder[nums[i]]==1) {
                return false;
            }else {
                recorder[nums[i]]++;
            }
            max = Math.max(max, nums[i]);
            min = Math.min(min, nums[i]);
        }
        return max - min < 5;
    }
}
